/*
 *  triangulate.cpp
 
 
 // COTD Entry submitted by John W. Ratcliff [jratcliff@verant.com]
 
 // ** THIS IS A CODE SNIPPET WHICH WILL EFFICIEINTLY TRIANGULATE ANY
 // ** POLYGON/CONTOUR (without holes) AS A STATIC CLASS.  THIS SNIPPET
 // ** IS COMPRISED OF 3 FILES, TRIANGULATE.H, THE HEADER FILE FOR THE
 // ** TRIANGULATE BASE CLASS, TRIANGULATE.CPP, THE IMPLEMENTATION OF
 // ** THE TRIANGULATE BASE CLASS, AND TEST.CPP, A SMALL TEST PROGRAM
 // ** DEMONSTRATING THE USAGE OF THE TRIANGULATOR.  THE TRIANGULATE
 // ** BASE CLASS ALSO PROVIDES TWO USEFUL HELPER METHODS, ONE WHICH
 // ** COMPUTES THE AREA OF A POLYGON, AND ANOTHER WHICH DOES AN EFFICENT
 // ** POINT IN A TRIANGLE TEST.
 // ** SUBMITTED BY JOHN W. RATCLIFF (jratcliff@verant.com) July 22, 2000
 
*******************************************************************************/

// INCLUDES ********************************************************************

#include "Triangulator.h"

#include "Vector2D.h"



static const float g_Epsilon = 0.0000000001f;

// NAMESPACES ******************************************************************

using namespace Meteor;

// *****************************************************************************

float Triangulator::Area( const std::vector<Vector2D>& contour)
{
	int n = contour.size();
	
	float A = 0.0f;
	
	for ( int p=n-1,q=0; q<n; p=q++)
	{
		A += contour[p].X() * contour[q].Y() - contour[q].X() * contour[p].Y();
	}
    
	return A * 0.5f;
}

// -----------------------------------------------------------------------------

bool Triangulator::InsideTriangle( float Ax, float Ay,
                                   float Bx, float By,
                                   float Cx, float Cy,
                                   float Px, float Py)

{
	float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
	float cCROSSap, bCROSScp, aCROSSbp;
	
	ax = Cx - Bx;  ay = Cy - By;
	bx = Ax - Cx;  by = Ay - Cy;
	cx = Bx - Ax;  cy = By - Ay;
	apx= Px - Ax;  apy= Py - Ay;
	bpx= Px - Bx;  bpy= Py - By;
	cpx= Px - Cx;  cpy= Py - Cy;
	
	aCROSSbp = ax*bpy - ay*bpx;
	cCROSSap = cx*apy - cy*apx;
	bCROSScp = bx*cpy - by*cpx;
	
	return ( ( aCROSSbp >= 0.0f) && ( bCROSScp >= 0.0f) && ( cCROSSap >= 0.0f));
}

// -----------------------------------------------------------------------------

bool Triangulator::Snip( const std::vector<Vector2D>& contour, 
                         int u, 
                         int v, 
                         int w, 
                         int n, 
                         int* V)
{
	int p;
    
	float Ax, Ay, Bx, By, Cx, Cy, Px, Py;
	
	Ax = contour[V[u]].X();
	Ay = contour[V[u]].Y();
	
	Bx = contour[V[v]].X();
	By = contour[V[v]].Y();
	
	Cx = contour[V[w]].X();
	Cy = contour[V[w]].Y();
	
	if ( g_Epsilon > ( ( ( Bx-Ax)*( Cy-Ay)) - ( ( By-Ay)*( Cx-Ax))) )
    {
        return false;
	}
    
	for ( p=0; p < n; p++)
	{
		if (  (p == u) || ( p == v) || ( p == w) ) 
        {
            continue;
        }
		
        Px = contour[V[p]].X();
		
        Py = contour[V[p]].Y();
		
        if ( InsideTriangle( Ax,Ay,Bx,By,Cx,Cy,Px,Py)) 
        {
            return false;
        }
	}
	
	return true;
}

// -----------------------------------------------------------------------------

bool Triangulator::Process( const std::vector<Vector2D>& contour, 
                            std::vector<Vector2D>& result)
{
    /* allocate and initialize list of Vertices in polygon */
	
	int n = contour.size();
	if ( n < 3 ) return false;
	
	int *V = new int[n];
	
	/* we want a counter-clockwise polygon in V */
	
	if ( 0.0f < Area(contour) )
		for (int v=0; v<n; v++) V[v] = v;
	else
		for(int v=0; v<n; v++) V[v] = (n-1)-v;
	
	int nv = n;
	
	/*  remove nv-2 Vertices, creating 1 triangle every time */
	int count = 2*nv;   /* error detection */
	
	for(int m=0, v=nv-1; nv>2; )
	{
		/* if we loop, it is probably a non-simple polygon */
		if (0 >= (count--))
		{
			//** Triangulate: ERROR - probable bad polygon!
			return false;
		}
		
		/* three consecutive vertices in current polygon, <u,v,w> */
		int u = v  ; if (nv <= u) u = 0;     /* previous */
		v = u+1; if (nv <= v) v = 0;     /* new v    */
		int w = v+1; if (nv <= w) w = 0;     /* next     */
		
		if ( Snip(contour,u,v,w,nv,V) )
		{
			int a,b,c,s,t;
			
			/* true names of the vertices */
			a = V[u]; b = V[v]; c = V[w];
			
			/* output Triangle */
			result.push_back( contour[a] );
			result.push_back( contour[b] );
			result.push_back( contour[c] );
			
			m++;
			
			/* remove v from remaining polygon */
			for(s=v,t=v+1;t<nv;s++,t++) V[s] = V[t]; nv--;
			
			/* resest error detection counter */
			count = 2*nv;
		}
	}
    
	delete V;
	
	return true;
}
